Semiring

In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse. The term rig is also used occasionally—this originated as a joke, suggesting that rigs are rings without negative elements.

Contents

Definition

A semiring is a set R equipped with two binary operations + and ·, called addition and multiplication, such that:[1]

  1. (R, +) is a commutative monoid with identity element 0:
    1. (a + b) + c = a + (b + c)
    2. 0 + a = a + 0 = a
    3. a + b = b + a
  2. (R, ·) is a monoid with identity element 1:
    1. (a·b)·c = a·(b·c)
    2. 1·a = a·1 = a
  3. Multiplication distributes over addition:
    1. a·(b + c) = (a·b) + (a·c)
    2. (a + b)·c = (a·c) + (b·c)
  4. 0 annihilates R, with respect to multiplication:
    1. 0·a = a·0 = 0

This last axiom is omitted from the definition of a ring: it follows automatically from the other ring axioms. Here it does not, and it is necessary to state it in the definition.

The difference between rings and semirings, then, is that addition yields only a commutative monoid, not necessarily a commutative group. Specifically, elements in semirings do not necessarily have an inverse for the addition.

The symbol · is usually omitted from the notation; that is, a·b is just written ab. Similarly, an order of operations is accepted, according to which · is applied before +; that is, a + bc is a + (bc).

A commutative semiring is one whose multiplication is commutative. An idempotent semiring (also known as a dioid) is one whose addition is idempotent: a + a = a, that is, (R, +, 0) is a join-semilattice with zero.

There are some authors who prefer to leave out the requirement that a semiring have a 0 or 1. This makes the analogy between ring and semiring on the one hand and group and semigroup on the other hand work more smoothly. These authors often use rig for the concept defined here.

Examples

In general

Specific examples

Semiring theory

Much of the theory of rings continues to make sense when applied to arbitrary semirings. In particular, one can generalise the theory of algebras over commutative rings directly to a theory of algebras over commutative semirings. Then a ring is simply an algebra over the commutative semiring Z of integers. Some mathematicians go so far as to say that semirings are really the more fundamental concept, and specialising to rings should be seen in the same light as specialising to, say, algebras over the complex numbers.

Idempotent semirings are special to semiring theory as any ring which is idempotent under addition is trivial. One can define a partial order ≤ on an idempotent semiring by setting a ≤ b whenever a + b = b (or, equivalently, if there exists an x such that a + x = b). It is easy to see that 0 is the least element with respect to this order: 0 ≤ a for all a. Addition and multiplication respect the ordering in the sense that a ≤ b implies ac ≤ bc and ca ≤ cb and (a+c) ≤ (b+c).

Further generalizations

A near-ring does not require addition to be commutative, nor does it require right-distributivity. Just as cardinal numbers form a semiring, so do ordinal numbers form a near-ring.

In category theory, a 2-ring is a category with functorial operations analogous to those of a ring. That the cardinal numbers form a ring can be categorified to say that the category of sets (or more generally, any topos) is a 2-ring.

Applications

Dioids, especially the (max, +) and (min, +) dioids on the reals, are often used in performance evaluation on discrete event systems. The real numbers then are the "costs" or "arrival time"; the "max" operation corresponds to having to wait for all prerequisites of an events (thus taking the maximal time) while the "min" operation corresponds to being able to choose the best, less costly choice; and + corresponds to accumulation along the same path.

The Floyd–Warshall algorithm for shortest paths can thus be reformulated as a computation over a (min, +) algebra. Similarly, the Viterbi algorithm for finding the most probable state sequence corresponding to an observation sequence in a Hidden Markov model can also be formulated as a computation over a (max, ×) algebra on probabilities. These dynamic programming algorithms rely on the distributive property of their associated semirings to compute quantities over a large (possibly exponential) number of terms more efficiently than enumerating each of them.

Semiring of sets

A semiring (of sets)[2] is a non-empty collection S of sets such that

  1. \emptyset \in S
  2. If E \in S and F \in S then E \cap F \in S.
  3. If E \in S and F \in S then there exists a finite number of mutually disjoint sets C_i \in S for i=1,\ldots,n such that E \setminus F = \cup_{i=1}^n C_i.

Such semirings are used in measure theory. An example of a semiring of sets is the collection of half-open, half-closed real intervals [a,b) \subset \mathbb{R}.

See also

Bibliography

  1. ^ Berstel & Perrin (1985), p. 26
  2. ^ Noel Vaillant, Caratheodory's Extension, on probability.net.